home *** CD-ROM | disk | FTP | other *** search
/ STraTOS 1997 April & May / STraTOS 1 - 1997 April & May.iso / CD01 / INTERNET / SITES / RAND / T0307 / text0023.txt < prev    next >
Encoding:
Text File  |  1997-02-06  |  4.7 KB  |  113 lines
  1.  
  2. Doug here,
  3.  
  4. > Yep, but I havn't tested it yet because of obvious reasons, but it depacks alright. 
  5.  
  6. > What 'obvious reasons'?  ;-)
  7.  
  8. I think Magnus should take a Falcon to his work. :)
  9.  
  10. > I tried it last night (yes, I know I should go to bed much earlier) and it
  11. > looked very nice indeed. Great work Doug!
  12.  
  13. Thanks. :)
  14.  
  15. > Now, what needs to be done before the sprites can be put in?
  16.  
  17. Well, as you know, it's not a straightforward job to drop the sprites in. I
  18. still have to do some more code to generate the sprite data for rendering, but
  19. that is not really a problem... 
  20.  
  21. > Since they're not in the BSP, I'd imagine (I haven't really thought about it)
  22. > that it isn't very obvious how they should be inserted at the right time
  23. > when drawing.
  24.  
  25. That's exactly what the problem is going to be - we will have to 'intercept'
  26. each ssector as it comes out of the tree, and insert the sprites at this
  27. point - but I believe I have a solution which will minimize all of the 'thing'
  28. management overheads.
  29.  
  30. If you can bear with me, I will describe the system I have in mind, which is
  31. a variation on a 'bucket array' using interleaved forward-linked lists. I think
  32. you will see that it makes our job a lot simpler, and provides the right information
  33. at exactly the right point in the program.
  34.  
  35. ---
  36.  
  37. Firstly, we have a simple 'sparse' array of pointers, one for each ssector.
  38. This pointer array is indexed using the ssector's own 16-bit index or 'name'. 
  39.  
  40. The pointers themselves are initialized to ZERO - which indicates that no
  41. objects are yet allocated to any ssector. There is a reason for not pointing
  42. the empty ssectors to a 'dummy' address instead, which I will explain later.
  43.  
  44. Secondly, we have a link-buffer full of linked list information, describing
  45. which objects belong to which ssectors, with a terminator at the end of
  46. each list.
  47.  
  48. Thirdly, we have a buffer full of object definitions - one per active object.
  49. These definitions consist of position information, intelligence 'states' and
  50. other object-specific stuff.
  51.  
  52. Assuming that the current number of ALLOCATED objects is defined as N, we
  53. can create an object-allocation subroutine which does the following:-
  54.  
  55. Allocate_Object:
  56.  
  57. * index pointer array and check list-pointer for this ssector.
  58.  
  59. * if pointer is VALID, then break the link at the very start
  60.   of the linked list indicated by this pointer address, and store
  61.   the link itself at offset (N*element_size) in the linked list buffer.
  62.  
  63. * if pointer is INVALID, then 'create' a new linked list for this
  64.   ssector by storing the object's link at offset (N*element_size)
  65.   in the linked list buffer, and update the pointer array to point
  66.   ot the new list, instead of zero. Terminate the forward link of
  67.   the new object by either linking it to a dummy object or with a
  68.   simple 0 / -1 terminator flag. 
  69.  
  70. * Increment N to reflect an increase in the number of total allocated
  71.   objects. Store the ssector's index in the object's definition along
  72.   with a back-link to aid deallocation of the object later on. 
  73.  
  74. This is a bit of an over-specific and detailed way to describe what
  75. is essentially a simple linked list maintenance job, but there are
  76. four good reasons for making it work in EXACTLY this way:-
  77.  
  78. a) By looking up the list-pointer array for any ssector which comes
  79.    off the BSP tree, we immediately have access to a linked list of
  80.    ALL the objects contained in that sector, and that sector ONLY.
  81.    This means we only draw what we can see, and nothing else.
  82.  
  83. b) There can be as many as one entire linked list per ssector - which
  84.    is a lot of lists - interleaving them in a single buffer this way
  85.    allows us to conserve an immense amount of memory, which would be
  86.    crippling if we reserved enough space for all objects, for all
  87.    possible ssectors.
  88.  
  89. c) Maintaining the sorted order of 'things' becomes part of the BSP's
  90.    job, at no extra cost. We only have to sort a nominal 2-5 objects
  91.    per VISIBLE ssector as opposed to tens or even hundreds per frame.
  92.    Even if it adds up to the same number of objects, it's still faster 
  93.    to perform lots of well-divided sorts than one very big one.
  94.  
  95. d) Maintaining the position of the 'things' themselves as they move
  96.    from ssector to ssector is even easier - each time they cross a
  97.    2-sided linedef, you use the object's back-link to it's perent list
  98.    to help you 'unlink' the object and use the index of the new ssector
  99.    to let you 'insert' the object back into the start of the new list
  100.    belonging to the target sector.
  101.  
  102. I hope I have made my thoughts clear on the operation of this system,
  103. but I believe it will ensure sorting & printing overheads are kept
  104. very very close to zero.
  105.  
  106. Of course, there may be additional improvements I have missed, and
  107. I would be glad to hear them. I just think this is a good place to
  108. start.
  109.  
  110. Doug.
  111.  
  112.  
  113.